// 1218. 最长定差子序列
// 给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。
// 子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

/**
 * @param {number[]} arr
 * @param {number} difference
 * @return {number}
 */
var longestSubsequence = function (arr, difference) {
  // 用 Map 取代 Array 优化子问题搜索
  const dp = new Map()

  let ans = 0
  for (const item of arr) {
    dp.set(item, (dp.get(item - difference) || 0) + 1)
    ans = Math.max(ans, dp.get(item))
  }

  return ans
}

console.log(
  longestSubsequence(
    [1, 5, 7, 8, 5, 3, 4, 2, 1],
    -2
  )
)












